package everydayone.sortArray;
/**
 * @Date 2020/03/31
 * @author 王光浩
 * @Thinking 使用并归排序，核心思想：分治法
 */
public class MyMethodSix {
	public int[] sortArray(int[] nums) {
		helper(nums,0,nums.length-1);
		return nums;
	}
	//进行并运算
	private void helper(int[] nums,int l,int r) {
		if(l>=r)return;
		//将l~r分成两份
		helper(nums,l,(r+l)/2);  //注意(r+l)/2这个公式
		helper(nums,(r+l)/2+1,r);
		merge(nums,l,r);
	}
	//进行归
	private void merge(int[] nums,int left,int right) {
		int[] temp=new int[right-left+1];
		int middle=left+(right-left)/2;
		int l=left;
		int r=middle+1;
		int index=0; 
		//将left~right部分的元素排序存放在temp中
		while(l<=middle && r<=right) {
			if(nums[l]>nums[r])temp[index++]=nums[r++];
			else temp[index++]=nums[l++];
		}
		//将左边剩下的直接加入temp中
		while(left<=middle)temp[index++]=nums[left++]; 
		//将右边剩下的直接加入temp中
		while(r<=right) temp[index++]=nums[right++];
		//将temp赋值到原数组中
		for(int i=0;i<temp.length;i++)nums[left++]=temp[i];
	}
}
